#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<unsigned long long> allfactor(unsigned long long n){
    
    //printf("2");
    vector<unsigned long long> a;
    for (unsigned long long i=2; i<=n; i++){
        if (n%i==0) a.push_back(i);
    }
    //printf("2");
    return a;
}

struct number{
    unsigned long long num;
    vector<unsigned long long> numbers;
};

unsigned long long operationtime(unsigned long long n){
    printf("%d\n",1);
    unsigned long long maxtime = 0;
    stack<struct number> stack1;
    unsigned long long time=0;
    unsigned long long i=0;
    struct number numb;
    numb.num=0;
    numb.numbers=allfactor(n);
    stack1.push(numb);
    //printf("%d\n",1);
    do {
        struct number numb=stack1.top();
        if (numb.num==numb.numbers.size()){
            stack1.pop();
            time--;
            if (stack1.empty())continue;
            struct number oldnumb=stack1.top();
            stack1.pop();
            n-=numb.numbers[oldnumb.num];
            oldnumb.num++;
            stack1.push(oldnumb);
            //printf("%d\n",oldnumb.numbers[0]);
        } 
        else{
            //printf("%d\n",1);
            struct number newnumb;
            unsigned long long index=numb.num;
            n-=numb.numbers[index];
            time++;
            if (time>maxtime)maxtime=time;
            
            stack1.pop();
            stack1.push(numb);//更新顶部
            if (n==0){
                numb.num++;
                continue;
            }
            vector<unsigned long long> a = allfactor(n);
            newnumb.num=0;
            newnumb.numbers=a;
            stack1.push(newnumb);
            //printf("%d\n",1);
        }
        
        
    }while (!stack1.empty());
    return maxtime;
}

int main(){
    int num;
    scanf("%d",&num);
    int result[num];
    for (unsigned long long i=0;i<num;i++){
        scanf("%d",&result[i]);
        
    }
    //printf("%d\n",1);
    for (unsigned long long i=0;i<num;i++){
        printf("%d\n",operationtime(result[i]));
    }

    return 0;
}